package com.sise.Tree;

/**
 *      654. 最大二叉树
 *
 *      给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 *
 *      二叉树的根是数组 nums 中的最大元素。
 *      左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 *      右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 *      返回有给定数组 nums 构建的 最大二叉树 。
 *
 *      输入：nums = [3,2,1,6,0,5]
 *      输出：[6,3,5,null,2,0,null,null,1]
 *      解释：递归调用如下所示：
 *      - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 *          - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 *              - 空数组，无子节点。
 *              - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 *                  - 空数组，无子节点。
 *                  - 只有一个元素，所以子节点是一个值为 1 的节点。
 *          - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 *              - 只有一个元素，所以子节点是一个值为 0 的节点。
 *              - 空数组，无子节点
 *
 *       题解：
 *          1、找终止条件：当 left > right，说明左右相交，数组中已经没有元素，那么就返回当前的节点为 null
 *          2、每一级递归返回的信息是什么：应当返回当前已经构造好的 最大二叉树 root 节点
 *          3、一次递归做了什么：找当前数组中的最大值作为 root 节点，并将其分为 [left， maxIndex - 1] 和 [maxIndex + 1， right]两段，
 *                           并分别构造成 root 的左右两棵树的最大二叉树
 *
 */
public class _654_MaximumBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maxTree(nums, 0, nums.length - 1);
    }

    public TreeNode maxTree(int[] nums, int left, int right){
        if (left > right) return null;                                      // 如果左右相交，那么则退出
        int maxIndex = findMax(nums, left, right);                          // 找到当前数组中的最大值
        TreeNode root = new TreeNode(nums[maxIndex]);                       // 为此最大值创建节点

        TreeNode leftNode = maxTree(nums, left, maxIndex - 1);                  // 由当前最大节点左右分开的 左右子节点
        TreeNode rightNode = maxTree(nums, maxIndex + 1, right);
        root.left = leftNode;                                               // 将其与当前节点相关联，最后递归向上一层返回当前层的节点
        root.right = rightNode;
        return root;
    }

    // 寻找数组中的最大值
    public int findMax(int[] nums, int left, int right){
        int max = Integer.MIN_VALUE;        // 最小值，比较后获取最大值
        int maxIndex = 1;                   // 为返回索引位置做准备
        for (int i = left; i <= right; i++){
            if (nums[i] > max){
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
